package com.mlamp;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Stack;

public class 判断括号合法性 {

    public static void main(String[] args) {

        判断括号合法性 instance = new 判断括号合法性();
        String[] inputs = new String[]{
                "[](){}",
                "()))((",
                "[(])",
                "[[(({{}}))]]"

        };
        for (String input : inputs) {
            System.out.print(instance.isValid(input) + " ");
            System.out.println(instance.isValid2(input));
        }

        System.out.println("----");

        for (String candidate : inputs) {
            System.out.print(instance.isValidC(candidate) + " vs ");
            System.out.println(instance.isValidCC(candidate));
        }
    }


    public boolean isValid34(String input) {
        int left = 0;
        for (char c : input.toCharArray()) {
            if (c == '(') left++;
            else left--;
            if (left < 0) return false;
        }
        return left == 0;
    }


    /**
     * 对于同类型的括号判断
     *
     * @param input
     * @return
     */

    public boolean isValidC(String input) {
        int left = 0;
        for (char c : input.toCharArray()) {
            if (c == '(') left++;
            else left--;
            if (left < 0) return false;
        }
        return left == 0;
    }


    //小试牛刀
    //这种情况只适合单一括号类型的判断，如果是多种括号都存在的情况，并不适用
    public boolean isValid(String input) {
        //带匹配的左括号
        int left = 0;
        for (char c : input.toCharArray()) {
            if (c == '(') left++;
            else left--;
            //提前收敛
            if (left < 0) return false;
        }
        return left == 0;
    }


    public boolean isValid33(String input) {
        int left = 0;
        char[] chars = input.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') left++;
            else left--;
            if (left < 0) return false;
        }
        return left == 0;
    }


    public boolean isValid1(String input) {
        int left = 0;
        for (char c : input.toCharArray()) {
            if (c == '(') left++;
            else left--;
            if (left < 0) return false;
        }
        return left == 0;
    }


    //单一括号的合法性判断
    public static boolean isValidA(String input) {
        if (input == null || input.isEmpty()) throw new IllegalArgumentException("invalid input");
        char[] inputs = input.toCharArray();
        int left = 0;
        for (char c : inputs) {
            if (c == '(') left++;
            else left--;
            if (left < 0) return false;
        }
        return left == 0;
    }


    /**
     * 基于栈数据结构判断括号的合法性
     *
     * @param input
     * @return
     */

    public static boolean isValidCC(String input) {
        if (input == null || input.length() == 0) return false;
        char[] chars = input.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : chars) {
            if (c == '(' || c == '{' || c == '[') stack.push(c);
            else if (!stack.isEmpty() && stack.peek() == leftOfA(c)) {
                stack.pop();
            } else return false;
        }
        return stack.isEmpty();

    }


    //正解
    // 使用栈替换
    //eg. [(])
    public boolean isValid2(String input) {
        Stack<Character> left = new Stack<>();
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') left.push(c);
            else if (!left.isEmpty() && leftOf(c) == left.peek()) left.pop();
            else return false;
        }
        return left.isEmpty();
    }

    public boolean isValid3(String input) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (!stack.isEmpty() && leftOf(c) == stack.peek()) stack.pop();
            else return false;
        }
        return stack.isEmpty();
    }


    public boolean isValidRegular(String input) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (!stack.isEmpty() && leftOf(c) == stack.peek()) stack.pop();
            else return false;
        }
        return stack.isEmpty();
    }


    public boolean isValid32(String input) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') stack.push(c);
            else if (!stack.isEmpty() && leftOf(c) == stack.peek()) stack.pop();
            else return false;
        }
        return stack.isEmpty();
    }


    public static boolean isValidAA(String input) {
        if (input == null || input.isEmpty()) throw new IllegalStateException("invalid input");
        char[] inputs = input.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') {
                stack.push(inputs[i]);
            } else if (!stack.isEmpty() && leftOfA(inputs[i]) == stack.peek()) {
                stack.pop();
            } else return false;
        }
        return stack.isEmpty();
    }


    public static boolean isValidB(String input) {
        if (input == null || input.trim().length() == 0) throw new IllegalArgumentException("invalid input");
        char[] inputs = input.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') stack.push(inputs[i]);
            else if (!stack.isEmpty() && leftOfA(inputs[i]) == stack.peek()) stack.pop();
            else return false;
        }
        return stack.isEmpty();
    }


    private static char leftOfA(char c) {
        if (c == ')') return '(';
        if (c == ']') return '[';
        if (c == '}') return '{';
        throw new IllegalStateException("invalid char");

    }


    private char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ']') return '[';
        return '(';
    }
}
